package org.example.myleet.rosalind.rnas;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {
    public static void main(String[] args) {
//        String rna = "AUGCUAGUACGGAGCGAGUCUAGCGAGCGAUGUCGUGAGUACUAUAUAUGCGCAUAAGCCACGU";
        String rna = "CGUGAGGUUAUAUCAUAAAGUUCCUGGGUCUAGAGUGUACACACUCGCAUCGAACACCGUGGUACAACGAGGAUUAUCUCAGGAGUCUAGCGAGUCACCACACCUGGUUAUUCGGACUACCGGACUCUCAGUGUUUCGCAUUCGACCAUUUUACAGAAUCCGCAGCCGGCAAGG";
        Map<String, BigInteger> memo = new HashMap<>();
        BigInteger res = calWobbleMotzkinNumber(rna, memo);
        System.out.println(res.toString());
    }

    private static BigInteger calWobbleMotzkinNumber(String seq, Map<String, BigInteger> memo) {
        BigInteger res = memo.get(seq);
        if (null != res) {
            return res;
        }
        if (seq.length() < 2) {
            return BigInteger.ONE;
        }
        BigInteger motzkinNumber = BigInteger.ZERO;
        List<Integer> matchIndices = getChar0MatchIndices(seq);
        for (int index : matchIndices) {
            //每一个和seq[0]匹配的位置都尝试连接并递归计算两边的Motzkin数并相乘得到当前匹配情况下的数量
            BigInteger leftMotzkinNumber = calWobbleMotzkinNumber(seq.substring(1, index), memo);
            BigInteger rightMotzkinNumber = calWobbleMotzkinNumber(seq.substring(index + 1), memo);
            motzkinNumber = motzkinNumber.add(leftMotzkinNumber.multiply(rightMotzkinNumber));
        }
        //Motzkin数还要加上seq[0]不做任何匹配的情况
        BigInteger prevMotzkinNumber = calWobbleMotzkinNumber(seq.substring(1), memo);
        motzkinNumber = motzkinNumber.add(prevMotzkinNumber);
        //记忆化
        memo.put(seq, motzkinNumber);
        return motzkinNumber;
    }

    private static List<Integer> getChar0MatchIndices(String seq) {
        List<Integer> res = new ArrayList<>(seq.length() - 1);
        char c0 = seq.charAt(0);
        for (int i = 4; i < seq.length(); ++i) {
            char c = seq.charAt(i);
            if (c0 == 'A' && (c == 'U' || c == 'T')) {
                res.add(i);
            } else if (c0 == 'U' && (c == 'A' || c == 'G')) {
                //允许Wobble的情况，U可以和G配对
                res.add(i);
            } else if (c0 == 'C' && c == 'G') {
                res.add(i);
            } else if (c0 == 'G' && (c == 'C' || c == 'U')) {
                //允许Wobble的情况，U可以和G配对
                res.add(i);
            }
        }
        return res;
    }
}
